package com.captain.special.二叉树.简单;

import com.captain.leetcode.TreeNode;

/**
 * Des:
 * 给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。
 * 高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
 *
 * @author XL
 * @Date 2022/5/6 16:43
 */
public class 将有序数组转换为二叉搜索树108 {
    public static void main(String[] args) {
        new 将有序数组转换为二叉搜索树108().sortedArrayToBST(new int[]{-10, -3, 0, 5, 9});
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return recur(nums, 0, nums.length - 1);
    }

    public TreeNode recur(int[] nums, int left, int right) {
        //1, 2, 3, 4, 5
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = recur(nums, left, mid - 1);
        root.right = recur(nums, mid + 1, right);
        return root;
    }
}
